package org.basis.algorithm.dp;

/**
 * 机器人走路问题
 *
 * @author Mr_wenpan@163.com 2022/03/17 18:59
 */
public class RobotWalk {

    public static void main(String[] args) {
        int walk = walk(5, 4, 4, 2);
        int walk3 = walk3(5, 4, 4, 2);
        System.out.println(walk);
        System.out.println(walk3);
    }

    public static int walk(int n, int e, int rest, int cur) {
        // 当前位置就在e上，并且剩余0步，返回1，表示1种走法（那就是不动）
        if (rest == 0 && cur == e) {
            return 1;
        }
        // 错误的数据
        if (rest < 0) {
            return -1;
        }
        return f(n, e, rest, cur);
    }

    /**
     * f函数(暴力递归版本)
     *
     * @param n    1 ~ n 这么多个位置 (固定参数)
     * @param e    目标位置 (固定参数)
     * @param rest 还剩多少步 (不固定参数)
     * @param cur  当前来到的位置 (不固定参数)
     * @return int 一共有多少种走法
     */
    public static int f(int n, int e, int rest, int cur) {
        // 如果还剩余0步
        if (rest == 0) {
            // 当前是否到达了目标位置？如果是则返回一种解，反之则返回0种解
            return cur == e ? 1 : 0;
        }
        // 如果当前来到了最左侧的位置，那么下一步决策只能往右走了（返回下一步往右走以后的决策结果）
        if (cur == 1) {
            return f(n, e, rest - 1, cur + 1);
        }
        // 如果当前来到了最右侧位置，那么下一步决策只能往左走一步了（返回下一步往左走以后的决策结果）
        if (cur == n) {
            return f(n, e, rest - 1, cur - 1);
        }
        // 如果当前位置来到了中间位置，那么他可以往左右两边走，所以最终得到的结果是由【往左走的子问题 + 往右走的子问题】的结果之和
        return f(n, e, rest - 1, cur - 1) + f(n, e, rest - 1, cur + 1);
    }

    public static int walk2(int n, int e, int rest, int cur) {
        // 当前位置就在e上，并且剩余0步，返回1，表示1种走法（那就是不动）
        if (rest == 0 && cur == e) {
            return 1;
        }
        // 错误的数据
        if (rest < 0) {
            return -1;
        }
        int[][] dp = new int[rest + 1][cur + 1];
        return f2(n, e, rest, cur, dp);
    }

    /**
     * f函数(记忆化搜索版本)
     * 由于这里有两个变参（rest和cur）所以需要一个二维数组来做缓存
     *
     * @param n    1 ~ n 这么多个位置 (固定参数)
     * @param e    目标位置 (固定参数)
     * @param rest 还剩多少步 (不固定参数)
     * @param cur  当前来到的位置 (不固定参数)
     * @return int 一共有多少种走法
     */
    public static int f2(int n, int e, int rest, int cur, int[][] dp) {
        // 如果还剩余0步
        if (rest == 0) {
            dp[rest][cur] = cur == e ? 1 : 0;
            // 当前是否到达了目标位置？如果是则返回一种解，反之则返回0种解
            return dp[rest][cur];
        }

        // 【先访问缓存，如果缓存里有值了，那么就不继续往下递归了，直接取缓存的值使用】
        if (dp[rest][cur] != -1) {
            return dp[rest][cur];
        }

        // 如果当前来到了最左侧的位置，那么下一步决策只能往右走了（返回下一步往右走以后的决策结果）
        if (cur == 1) {
            dp[rest][cur] = f2(n, e, rest - 1, cur + 1, dp);
            return dp[rest][cur];
        }
        // 如果当前来到了最右侧位置，那么下一步决策只能往左走一步了（返回下一步往左走以后的决策结果）
        if (cur == n) {
            return dp[rest][cur] = f2(n, e, rest - 1, cur - 1, dp);
        }
        // 如果当前位置来到了中间位置，那么他可以往左右两边走，所以最终得到的结果是由【往左走的子问题 + 往右走的子问题】的结果之和
        dp[rest][cur] = f2(n, e, rest - 1, cur - 1, dp) + f2(n, e, rest - 1, cur + 1, dp);
        return dp[rest][cur];
    }

    /**
     * 最终需要求的是从cur位置出发，到达end位置，走rest步，有几种走法
     * 所以也就是求的dp[cur][rest]的值，也就是根据已知的值推导出dp[cur][rest]的值
     */
    public static int walk3(int n, int e, int rest, int cur) {
        int[][] dp = new int[rest + 1][n + 1];
        // 初始化已知的值(当cur到达end处，并且剩余步数为0时，该处的值为1)
        dp[0][e] = 1;

        // 遍历二维数组每个位置，求得目标值
        for (int i = 1; i <= rest; i++) {
            for (int j = 1; j <= n; j++) {
                // cur在最左边的位置
                if (j == 1) {
                    dp[i][j] = dp[i - 1][j + 1];
                }
                // 如果cur处于最右边的位置
                if (j == n) {
                    dp[i][j] = dp[i - 1][j - 1];
                } else {
                    // 如果cur位于中间
                    dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j + 1];
                }
            }
        }

        return dp[cur][rest];
    }
}
